1. Field of the Invention
The present invention relates to a new class of reversible nonlinear feedback shift registers (also referred to herein as NLFSR's), and more particularly, to the generalization of suitable NLFSR's in terms of a multi-parameter family of nonlinear discrete dynamical systems. One useful application of this invention is to the encryption and decryption of digital information reversibly, flexibly, and rapidly.
2. Description of the Prior Art
It is known to encrypt information to secure the information from unintended use by unauthorized persons or devices. In general such data encryption uses a key value in conjunction with pseudo-random processing techniques to transform the information. The unencrypted information comprises a string of symbols which are collectively referred to as plaintext. Encoding/encrypting the plaintext string using the key value produces a ciphertext string. Reversing the process of the encryption, i.e., decryption, requires use of the same key value.
FIG. 2 is a block diagram depicting the general flow of information in a system which encrypts information. A transmitting element 1000 in which is embodied an encryption algorithm received a plaintext string 1004 and a key 1006 as inputs. The encryption algorithm in transmitting element 1000 is applied to the plaintext string 1004 under control as defined by the key 1006. The resulting ciphertext string 1003 is then (eventually) applied to a receiving element 1001 in which is embodied a decryption algorithm. The decryption algorithm within receiving element 1001 receives the ciphertext string 1003 and the key 1007 as inputs and produces the plaintext string 1005 as output.
If the keys 1006 and 1007 are the same, the decryption algorithm in receiving element 1001 reverses the processing performed by the encryption algorithm in transmitting element 1000. In such a case, the plaintext string 1005 produced by the receiving element 1001 matches the plaintext string 1004 provided as input to the encryption algorithm in transmitting element 1000. If the keys 1006 and 1007 do not match, the plaintext string 1005 will not match the original plaintext string 1004. The ciphertext string 1003 is thereby secured from unintended use by persons or devices which are not in possession of the proper key (1006 and 1007).
The system of FIG. 2 is exemplary of several applications of encryption/decryption processes. For example, elements 1000 and 1001 may be processes within a general purpose computer for storing an encrypted ciphertext string in a mass storage file then later retrieving it and decrypting the stored information. Or, for example, elements 1000 and 1001 may be communicating devices, such radio or telephonic voice communication devices, or data communication devices (modems), or facsimile devices, etc. FIG. 2 is therefore intended to represent any system which utilizes encryption and/or decryption of information.
The process of attempting to derive the plaintext which corresponds to a ciphertext without access to the key is often referred to as cryptanalysis or a cryptanalytic attack. Prior art techniques for encryption suffer a variety of problems, including the fact that many fall victim to cryptanalytic techniques which can derive the plaintext from the cyphertext. Such prior techniques are therefore insecure for encryption of highly sensitive information.
Prior techniques for encryption tend to balance level of security against computational complexity. Some prior techniques offer significant security against cryptanalytic techniques but at a significant cost in complexity of computation. Other prior methods offer simpler computation but at a cost of lessened security against cryptanalytic attack.
One prior technique for encryption uses feedback shift registers to encrypt/decrypt information. The theoretical considerations and practical implementations of feedback shift registers (FSR's) are well-known as presented, for example, in U.S. Pat. No. 5,365,589, issued to Gutowitz on Nov. 15, 1994 and in Applied Cryptography, 2.sup.nd Ed. John Wiley and Sons, Inc. by B. Schneier (1996).
An FSR generally consists of two parts as shown in FIG. 1: an n bit shift register 901 comprising n bits 902 (B.sub.1 . . . B.sub.n), and a feedback function 905. Each bit 902 of shift register 901 may be applied to feedback function 905 via path 904 in accordance with the tap sequence defined for the FSR. Certain combinations of the values of each bit are used as inputs to the feedback function, and each bit computed by the feedback function 905, is fed back into the first bit in the shift register 901 via path 903. The clocked output of the shift register 901 is applied to path 900 for use in producing the ciphertext string from the plaintext string. The sequence of bits thereby produced can represent a pseudo-random sequence which is used by encryption algorithms to produce a ciphertext string from an input plaintext string. The process can be reversed to generate the original plaintext string from a ciphertext string.
If the feedback function is the XOR logical function, (or the sum `modulo 2`), of certain bits in the shift register then the FSR is called a linear feedback shift register (LFSR). Associated with each bit in the shift register is a weight that defines how much the corresponding bit contributes to the feedback function. A list of these weights is called the tap sequence of the LFSR.
A binary n bit LFSR is one in which each element of the shift register takes on one of two values, e.g., 0 or 1. Such a binary LFSR can be in one of 2.sup.n -1 nontrivial states. It is well known that only certain tap sequences will cause an LFSR to cycle through all of these 2.sup.n -1 states in a complex, pseudo-random fashion. In order for an LFSR to cycle through this maximum number of states, the polynomial formed from the tap sequence plus the integer 1 must be a primitive polynomial `modulo 2.`
There are three immediate difficulties with using an LFSR to generate complex output sequences. First, there is no simple way to generate primitive polynomials `mod 2` other than by choosing a random polynomial and testing if it is primitive. Second, in order to generate suitably complex output sequences the LFSR should have a large number of non-zero taps. However, it is, in general, difficult to generate primitive polynomials with a large number of non-zero taps. Finally, an LFSR can be completely characterized using 2n bits of an output sequence via the Berlekamp-Massey algorithm (see Schneier, supra.). In general, it is difficult to use an LFSR to combine elements of an input sequence in a suitably complex fashion. See Schneier (supra.) and references therein for a discussion of LFSR's and their properties.
It is apparent from the above discussion that improved encryption/decryption techniques are desired which provide both improved security against cryptanalytic attack and simplified computation.